//给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：[[1,2,3],[8,9,4],[7,6,5]]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[[1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 20 
// 
// Related Topics 数组 矩阵 模拟 
// 👍 548 👎 0

package com.cute.leetcode.editor.cn;
public class SpiralMatrixIi {
    public static void main(String[] args) {
        new SpiralMatrixIi().new Solution().generateMatrix(4);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] generateMatrix(int n) {
            int[][] res = new int[n][n];
            int num = 1;
            int max = n*n;
            // 设定一个前进方向 1向右 -1向左 2向下 -2向上，在当前方向一定要走到头才能转向
            int direction = 1;
            for (int i = 0; i < n;) {
                for (int j = 0; j < n; ) {
                    res[i][j] = num++;
                    //这里是判断结束位置
                    if (num>max) return res;

                    if (direction == 1){//向右
                        if (j+1 < n && res[i][j+1] == 0) j++;
                        else{
                            direction=2;
                            i++;
                        }
                    }
                    else if (direction == 2){//向下
                        if (i+1 < n && res[i+1][j] == 0) i++;
                        else {
                            direction = -1;
                            j--;
                        }
                    }
                    else if (direction == -1){//向左
                        if (j-1 >= 0 && res[i][j-1] == 0) j--;
                        else {
                            direction = -2;
                            i--;
                        }
                    }
                    else {//向上
                        if (i-1 >= 0 && res[i-1][j] == 0) i--;
                        else {
                            direction = 1;
                            j++;
                        }
                    }
                }
            }
            return res;
        }

        /**
         * 定义上下左右四个边界
         * l：左边界
         * r：右边界
         * t：上边界
         * b：下边界
         * 遍历时按照右下上左的顺序进行
         */
        public int[][] generateMatrix2(int n) {
            int[][] res = new int[n][n];
            int num = 1,max = n*n;
            int l = 0;
            int r = n-1;
            int t = 0;
            int b = n-1;
            while (num<=max){
                for (int i = l; i <= r; i++) res[t][i] = num++;//左到右，结束后上边界++
                t++;
                for (int i = t; i <= b; i++) res[i][r] = num++;//上到下，结束后右边界--
                r--;
                for (int i = r; i >= l; i--) res[b][i] = num++;//右到左，结束后下边界--
                b--;
                for (int i = b; i >= t; i--) res[l][i] = num++;//下到上，结束后左边界++
                l++;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}



































